package cn.qyd.leecode;

/**
 * @author 邱运铎
 * @date 2024-04-05 21:58
 */

import sun.reflect.generics.tree.Tree;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class TwoForkTree002 {
    private static int maxDiff = -1;

    public static void main(String[] args) {
//        TreeNode treeNode1 = new TreeNode(1);
//        TreeNode treeNode4 = new TreeNode(4);
//        TreeNode treeNode7 = new TreeNode(7);
//        TreeNode treeNode13 = new TreeNode(13);
//        TreeNode treeNode6 = new TreeNode(6, treeNode4, treeNode7);
//        TreeNode treeNode3 = new TreeNode(3, treeNode1, treeNode6);
//        TreeNode treeNode14 = new TreeNode(14, treeNode13, null);
//        TreeNode treeNode10 = new TreeNode(10, null, treeNode14);
//        TreeNode treeNode8 = new TreeNode(8, treeNode3, treeNode10);

        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode0 = new TreeNode(0, treeNode3, null);
        TreeNode treeNode2 = new TreeNode(2, null, treeNode0);
        TreeNode treeNode1 = new TreeNode(1, null, treeNode2);
        TwoForkTree002 twoForkTree002 = new TwoForkTree002();
        int i = twoForkTree002.maxAncestorDiff(treeNode1);
        System.out.println(i);

    }
    public int maxAncestorDiff(TreeNode root) {
        if (root == null) return -1;
        dfs(root,root.val, root.val);
        return maxDiff;
    }

    public void dfs(TreeNode node, int little, int more) {
        TreeNode leftNode = node.left;
        TreeNode rightNode = node.right;
        if (leftNode == null && rightNode == null) {
            maxDiff = Math.max(maxDiff, more - little);
        }
        int curLittle = little;
        int curMore = more;
        if (leftNode != null) {
            int val = leftNode.val;
            if (val < curLittle) {
                curLittle = val;
            }
            if (val > curMore) {
                curMore = val;
            }
            dfs(leftNode, curLittle, curMore);
            curLittle = little;
            curMore = more;
        }

        if (rightNode != null) {
            int val = rightNode.val;
            if (val < curLittle) {
                curLittle = val;
            }
            if (val > curMore) {
                curMore = val;
            }
            dfs(rightNode, curLittle, curMore);
        }
    }
}
